%Configuracion del documento

%Tamaño de letra principal:
\documentclass[12pt]{article}

%Título y autor(es):
\title{Título del TP}
\author{Sergio}

%Tamaño de página y los márgenes:
\usepackage[a4paper,headheight=16pt]{geometry}
\textwidth      =  450pt     %Ancho del cuerpo
\textheight     =  648pt     %Largo del cuerpo
\topmargin      =  0pt       %Agrega espacio en el margen superior
\oddsidemargin  =  0pt       %+ margen izquierdo en paginas impares
\evensidemargin =  0pt       %+ margen derecho en paginas impares

% Vamos a escribir en castellano:
\usepackage[spanish]{babel}

%instalar texlive-lang-spanish
% Reconocer acentos y caracteres no ingleses:
\usepackage[utf8]{inputenc}

% Cabecera y pie de página personalizadas
\usepackage{fancyhdr}
\pagestyle{fancy}

% Hago que en la cabecera de página se muestre a la derecha la sección,
% y en el pie, en número de página a la derecha:
\renewcommand{\sectionmark}[1]{\markboth{}{\thesection\ \ #1}}
\lhead{}
\chead{}
\rhead{\rightmark}
\lfoot{}
\cfoot{}
\rfoot{\thepage}

%numeracion especial para tablas, figuras y ecuaciones
\usepackage{amsmath}
\numberwithin{equation}{section}
\numberwithin{figure}{section}
\numberwithin{table}{section}

%Agregar notas al pie en tablas:
\usepackage{threeparttable}

%Incluir Graficos
\usepackage{graphicx}

%Imágenes no flotantes, se colocan donde les decís que aparezcan cambiando [h] por [H]
\usepackage{float}

%Usar subfiguras: (al estilo Figura 2.3(b) )
\usepackage{subfigure}

% Para esto es necesario texlive-latex-recommended o texlive-latex-extra
%Numero de figuras en negrita
\usepackage[hang,bf]{caption}
\usepackage{enumerate}
% Todas las imágenes están en el directorio tp-img:
\newcommand{\imgdir}{tp-img}
\graphicspath{{\imgdir/}}

% uso de colores
\usepackage{color}
\definecolor{gray}{rgb}{0.9,0.9,0.9}

%Para embeber código de lenguajes como Matlab, C, html, etc.
\usepackage{float}
\usepackage{listings}
\lstset{ frame=Ltb, 
	framerule=0pt, 
	aboveskip=0.5cm, 
	framextopmargin=3pt, 
	framexbottommargin=3pt, 
	framexleftmargin=0 cm, 
	framesep=0pt, rulesep=.3pt, 
	backgroundcolor=\color{gray}, 
	rulesepcolor=\color{black}, 
	showstringspaces = false, 
	basicstyle=\small\ttfamily, 
	commentstyle=\color{gray}, 
	keywordstyle=\bfseries
	}

	%rulesepcolor=\color{black},
	%stringstyle=\ttfamily,
	%showstringspaces = false,
	%basicstyle=\small\ttfamily,
	%commentstyle=\color{gray},
	%keywordstyle=\bfseries,

	%numbers=left,
	%numbersep=15pt,
	%numberstyle=\tiny,
	%numberfirstline = false,
	%breaklines=true

%Para colocar hipervinculos
%\usepackage[dvipdfm,colorlinks=true,linkcolor=black,urlcolor=blue]{hyperref}
%Para hacer matrices y digramas de flujo sencillos

%\usepackage[all]{xy}

%INICIO DEL DOCUMENTO

\begin{document}

\begin{titlepage}

% Sin cabecera ni pie de página:
\thispagestyle{empty}

% Logo de la facu: 
\begin{center}
	\includegraphics[width=8cm]{logo-facu}
\end{center}
\vfill

% Título:
\begin{center}
	\Huge{75.29 Teoría de Algoritmos}\\
	\Huge{Trabajo Práctico Nro 1}\\
	\Large{Problema de las parejas estables}\\
\end{center}
\vspace{3cm}

% Integrantes:
\large{
	\begin{tabbing}
		Sergio Hinojosa \hspace{1cm} \\84476 \\
		shinojosa@fi.uba.ar\\
		\\
		Fernando Mansilla \hspace{1cm} \\84567 \\
		fernando.e.mansilla@gmail.com\\
	\end{tabbing}
}
\vfill

% Fecha o cuatrimestre:
\flushright{2011}
\end{titlepage}

% Hago que las páginas se comiencen a contar a partir de aquí:
\setcounter{page}{1}

%INDICE
%-------------------------------------------------------------------------------
% Pongo el índice en una página aparte:
\tableofcontents
\newpage
%-------------------------------------------------------------------------------

% Inicio del TP:

\section{Enunciado}

Ustedes han sido contratados como casamenteros de una comunidad muy cerrada, formada por N hombres y N mujeres, todos solteros, y que deben casarse (todos) entre sí este año. Basarán su asignación en las preferencias de cada uno (es decir que le pedirán a cada hombre que haga un ranking de todas las mujeres, calificándolas de 1 a N, y de igual modo le pedirán a cada mujer que haga un ranking de todos los hombres). Para mantener
la buena fama de casamenteros que tienen (que los ha hecho muy solicitados por diversas comunidades) deben evitar que los matrimonios se separen al poco tiempo. En particular quieren evitar armar parejas inestables (decimos que estamos en una situación inestable si un hombre y una mujer que están casados con otros preferirían estar casados entre sí).\\

El problema de armar las parejas sin que haya una situación inestable se conoce como el problema de los matrimonios estables. Trabajaremos con los siguientes conceptos:

\begin{itemize}
    \item Un par hombre-mujer es un par bloqueante de la asignación si están en pareja con otros cuando preferirían estar en pareja entre sí.
    \item Una asignación es estable si no contiene ningún par bloqueante (y es inestable si contiene alguno).
\end{itemize}

Si se asignara (a;L), (b; J), (c;M), (d;K) entonces (a; J) resultaría un par bloqueante (y por lo tanto (a;L), (b; J), (c;M), (d;K) resultaría una asignación inestable, en la cual a y J terminarían separándose de sus respectivas parejas para casarse entre sí, ya que cada uno de ellos estaría casado con otro/a pese a que a eligió a J en primer lugar y J eligió a a en primer lugar. En cambio (a; J), (b;L), (c;M), (d;K) es una asignación
estable. Una manera de realizar una asignación estable es por backtracking. Sin embargo, existe un algoritmo (de Gale \& Shapley, 1962) que es más eficiente, ya que tiene orden polinomial en la cantidad de personas.

\subsection{Algoritmo de Gale y Shapley}
El algoritmo procede por rondas:

\begin{itemize}
    \item En la primera ronda cada hombre se le declara a la mujer que prefiere independientemente de que algún otro se le haya declarado. Entre todas las propuestas que recibió, cada mujer elige al hombre mejor posicionado en su ranking y se compromete con él. Si una mujer no recibe ninguna propuesta, espera hasta la próxima ronda.
    \item En cada ronda subsiguiente los hombres que ya estén comprometidos no hacen nada. Cada hombre no comprometido se le declara a la mujer mejor posicionada en su ranking que aún no lo rechazó, independientemente de que ella esté comprometida o no. Cuando le toca el turno a las mujeres, cada mujer acepta la propuesta del hombre mejor posicionado en su ranking (incluso puede llegar a romper un compromiso; también puede suceder que su novio actual esté mejor posicionado que todos sus nuevos pretendientes, en cuyo caso se queda con el novio actual). Si una mujer no recibe ninguna propuesta, espera hasta la próxima ronda.
    \item Mientras queden hombres no comprometidos al final de una ronda, se hace una nueva ronda.
\end{itemize}

\subsection{Se pide:}

\begin{enumerate}
\item Resolver el problema por backtracking.
    \begin{enumerate}
    \item Calcular el orden.
    \end{enumerate}
\item Programar el algoritmo de Gale \& Shapley para resolver el problema.
    \begin{enumerate}
    \item Elegir las estructuras de datos adecuadas para implantar eficientemente el algoritmo y calcular el orden. Justificar.
    \item Justificar que la asignación es completa y estable, es decir que el algoritmo no deja personas solteras y la asignación realizada es estable.
    \item Justificar que el algoritmo termina siempre.
    \item ¿El algoritmo es simétrico? Justificar.
    \item Si se les permitiera a las mujeres cambiar la lista de de preferencia durante la ejecución del algoritmo, como podría hacer una mujer dada, para conseguir el hombre óptimo.
    \item Explicar de que estrategia algorítmica se trata. Justificar.
    \end{enumerate}
\end{enumerate}

\clearpage

\section{Backtraking}

\begin{lstlisting}
#!/usr/bin/python
# -*- coding: utf-8 -*-

H = [[0,1,2,3],[3,2,0,1],[3,2,0,1],[1,0,2,3]]
M = [[0,2,1,3],[3,1,2,0],[0,3,1,2],[2,3,0,1]]
parejas = [-1,-1,-1,-1]
mlibre = [True,True,True,True]
hlibre = [True,True,True,True]

def estable(hombre,mujer,preferencia):
    """Si hay un soltero que prefiere a la mujer antes que el 
    orden de preferencia de hombre, (hombre, mujer) no sera 
    una pareja estable"""
    
    i = 0
    while M[mujer][i] != hombre:
        if hlibre[M[mujer][i]]:
            for i in range(0,preferencia-1):
                if H[hombre][i] == mujer:
                    return false
        i += 1
    return True

def pareja(hombre):
    for preferencia in range(0,3):
        print hombre
        print parejas
        mujer = H[hombre][preferencia]
        if mlibre[mujer] and estable(hombre,mujer,preferencia):
            parejas[hombre] = mujer
            mlibre[mujer] = False
            hlibre[mujer] = False
            if hombre < 3 :
                if not(pareja(hombre+1)):
                    mlibre[mujer] = True
            else:
                return True
    return False

if __name__ == "__main__":
    pareja(0)
    print parejas
\end{lstlisting}

\clearpage

\section{Algoritmo de Gale y Shapley}

\begin{lstlisting}
#!/usr/bin/python
# -*- coding: utf-8 -*-

H = [[0,1,2,3],[3,2,0,1],[3,2,0,1],[1,0,2,3]]
M = [[0,2,1,3],[3,1,2,0],[0,3,1,2],[2,3,0,1]]
parejas = [-1,-1,-1,-1]
mlibre = [3,2,1,0]
hlibre = [3,2,1,0]

def pareja():
    while (hlibre != []):
        hombre = hlibre.pop()
        mujer = H[hombre][0]
        if (mujer in mlibre):
            mlibre.remove(mujer)
            H[hombre].remove(mujer)
            parejas[hombre] = mujer
        else:
            actual = parejas.index(mujer)
            if M[mujer].index(hombre)<actual:
                hlibre.append(actual)
                parejas[actual] = -1
                parejas[hombre] = mujer
            else:
                hlibre.append(hombre)

if __name__ == "__main__":
    pareja()
    print parejas
\end{lstlisting}

\subsection*{Justificar que la asignación es completa y estable, es decir que el algoritmo no
deja personas solteras y la asignación realizada es estable.}

La asignación es completa\\

Cuando una mujer se casa, siempre se casa con alguien. Por lo tanto, al final, no pueden existir un hombre y una mujer ambos sin casarse, debido a que el homber debe haber propuesto matrimonio a la mujer en algun punto (teniendo en cuenta que un hombre eventualmente propone casamiento a todas las mujeres si es necesario). Además, en el caso de que una mujer se separe, lo hará para casarse con otro hombre, por lo que seguira casada.\\

Las asignaciones son estables\\

Supongamos la pareja de Carla y Juan, ambos casados pero no entre sí. Luego de la finalización del algoritmo, no es posible para Carla y Juan que se prefieran el uno al otro por encima de sus parejas actuales. Si Juan prefiere a Carla en vez de a su pareja actual, el debe haberle propuesto casamiento a Carla antes de haberselo propuesto a su pareja actual. Si Carla acepto esa propuesta, y si aún no esta casada con el al final, es porque se separo dejándolo por alguien al que ella prefiera más, y por lo tanto no prefiere a Juan más que a su pareja actual.
Si Carla rechazó su propuesta, ella seguirá casada con alguien al que ella prefiere más que a Juan.

\subsection*{Justificar que el algoritmo termina siempre.}

Primero, debemos demostrar que ningún hombre será rechazado por todas las mujeres. Una mujer puede rechazar solo cuando ella está casada, siendo que una vez que ella esta casada nunca volverá a estar soltera. Por lo tanto el rechazo por un hombre por parte de la última mujer de su lista implicaría que todas las mujeres ya se encuentran casadas. Pero dado que hay un número igual de hombres y mujeres, y ningún hombre tiene 2 prometidas, todos los hombres estarían también casados, lo cual es una contradicción. También cada iteración involucra una propuesta, y ningún hombre propone dos veces casamiento a la misma mujer, por lo tanto el número de iteraciones no puede exceder $n^2$ (suponiendo que hay n hombre y n mujeres). Por lo tanto el algoritmo termina.

\subsection*{¿El algoritmo es simétrico? Justificar.}
El algoritmo no es simétrico dado que la asignación es óptima para los hombres (todos los hombres consiguen a su mejor pareja válida) y en contrapartida las mujeres consiguen a su peor pareja válida.\\

Demostración:\\

Supongamos que esto es falso (que las mujeres no consiguen a su peor pareja válida). Sea M0 el matcheo estable óptimo para los hombres y supongamos que existe un matcheo estable M' y una mujer w tal que esta prefiere a m = pM0(w) frente a m' = pM'(w). Pero luego (m, w) bloquea a M' a menos que m prefiera pM'(m) antes que w = pM0(m), en contradicción al hecho de que m no tiene un compañero estable mejor que su compañero en M0.

Notación:\\

pM'(m) $\rightarrow$ compañero de m en M'

\subsection*{Si se les permitiera a las mujeres cambiar la lista de de preferencia durante la ejecución del algoritmo, como podría hacer una mujer dada, para conseguir el hombre óptimo.}

La mujer debería mentir, conociendo las preferencias de todos los demás, de forma tal de que los hombres que se le proponen vayan siendo aceptados y descartados (hasta conseguir al pretendiente buscado) haciendo que el pretendiente deseado sea abandonado por sus parejas y no le quede más que quedarse con la mujer tramposa.



\end{document}
